package com.wz.leetcode.dp_greedy;

import java.util.Arrays;

public class TaskScheduler_621 {
    public static int leastInterval(char[] tasks, int n) {
        int[] buckets = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            buckets[tasks[i] - 'A']++;
        }
        Arrays.sort(buckets);
        int maxTimes = buckets[25];
        int maxCount = 1;
        for (int i = 25; i >= 1; i--) {
            if  (buckets[i] == buckets[i-1]) {
                maxCount++;
            } else {
                break;
            }
         }
        int result = (maxTimes - 1) * (n + 1) + maxCount;
        // 如果任务种类很多，在安排时无需冷却时间，只需要在一个任务的两次出现间填充其他任务，
        // 然后从左到右从上到下依次执行即可，由于每一个任务占用一个时间单位，
        // 我们又正正好好地使用了tasks中的所有任务，
        // 而且我们只使用tasks中的任务来占用方格（没用冷却时间）。
        // 因此这种情况下，所需要的时间即为tasks的长度。
        return Math.max(result, tasks.length);
    }
}
